МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Інститут телекомунікацій, радіоелектроніки та електронної техніки
/
Розрахунково-графічна робота
з дисципліни "Комп'ютерна оптимізація проектних рішень"
МЕТА РОБОТИ
Опанування теоретичних засад і набуття навичок практичного застосування інструменту Solver Microsoft Excel для розв'язання традиційної та нетрадиційної транспортної задачі і задач, що зводяться до транспортної.
ЗАВДАННЯ
Варіант 1. Телевізійна компанія планує підключення до своєї кабельної мережі п’яти нових районів. На рисунку нижче показана структура мережі, що буде створюватися, і відстань у км між районами та телецентром (п. 1). Спланувати найкоротшу кабельну мережу.
/
Рис. 1. Структура мережі.
ПОШУК РІШЕННЯ
За справжній пункт пропозиції з обсягом пропозиції 1 приймемо вершину і=1, решту вершин розглянемо як транзитні пункти попиту з обсягом попиту bj=1, j = 2(6. Оскільки граф має w = 6 вершин, то обсяг буферу приймемо B=w-1=5. Матриця невідомих набуває розмірності (п)((п-1); серед пунктів попиту відсутній лише п. 1 (справжній пункт пропозиції) (рис. 1).
/
Рис. 2. Модель задачі для пошуку мінімального остівного дерева на графі (рис. 1) як транзитної транспортної задачі (Т-задачі) з умовою балансу потоків у Solver MS Excel.
Розрахунок моделей за допомогою Solver MS Excel
Реалізація моделі задачі у MS Excel відображена у табл. 1.
Таблиця 1
Реалізація елементів моделі задачі для пошуку мінімального остівного дерева на графі (рис. 1) як транзитної Т-задачі (рис. 2) на аркуші MS Excel
Адреса комірки
Формула
Розповсюдже-на на комірки
Зміст, виконуване завдання
1
2
3
4
D4:H9
Транспортна таблиця (матриця) невідомих, яка є редукованою матрицею суміжності остаточного графа, який відповідає маршруту перевезень
D14:H19
Чисельні значення відстаней між суміжними вершинами
Транспортна таблиця (матриця) вартостей, яка містить значення відстаней між суміжними вершинами
D22:H27
0(1
Редукована матриця суміжності вихідного графа; задає обмеження на структуру остаточного графа
Q17
5, чисельне значення обсягу пропозиції у п. 1
Обсяг пропозиції у п.1, прийнятому за справжній пункт пропозиції, за (25)
Q19
1, чисельне значення справжнього попиту у всіх вершинах графа, крім п.1
Чисельне значення справжнього по-питу у всіх вершинах графа, прийняв-тих за транзитні пункти попиту
1
2
3
4
Q18
=МАКС(Q17;Q19)
Чисельне значення обсягу буфера, розраховане за (6)
J5
=$Q$19+$Q$18
J5:J9
Чисельне значення граничного обсягу пропозиції у транзитних пунктах попиту за (10)
D11
=$Q$19+$Q$18
D11:H11
Чисельне значення граничного обсягу попиту у транзитних пунктах попиту за (11)
D10
=СУММПРОИЗВ(D4:D9;D22:D27)
D10:H10
Обсяг «пропозиції», ввезеної у кожну вершину графа, прийняту за транзитний пункт попиту, з урахуванням обмежень на структуру графа (СУММ – дає суму по рядку, а ПРОИЗВ забезпечує не включення у остаточний граф неіснуючих у вихідному графу ребер завдяки обмеженню балансу потоків)
I4
=СУММПРОИЗВ(D4:H4;D22:H22)
I5:I9
Обсяг «пропозиції», вивезеної з кожної вершини графа з урахуванням обмежень на структуру графа
О5:О9
{=ТРАНСП(D10:I14)}
Формула масиву
Сумарний обсяг «вантажу», ввезеного у кожну з вершин графа, прийняту за транзитний пункт попиту за (14), (27) (сумарний вхідний потік)
Р5
=I5
Р5:Р9
Сумарний обсяг вантажу, вивезеного кожної з вершин графа, прийнятої за транзитний пункт попиту за (14), (27) (сумарний вихідний потік)
Q5
=O5-1
Q6:Q9
Сумарний обсяг вантажу, який має бути вивезений з кожного з транзитних пунктів попиту за (14), (27) для задоволення попиту у 1, тобто для забезпечення «остівності» дерева
С29
=СУММПРОИЗВ(D4:H9;D14:H19)
Цільова функція – мінімальне остівне дерево за (23)
Постановка зазначеної задачі як оптимізаційної передбачає ідентифікацію у діалоговому вікні Пошуку рішення надбудови Solver (Пошук рішення) MS Excel: типу екстремуму (мінімум); адрес комірок, які містить ціл...
